//
// 队列
//

#include <iostream>
#include <memory>

template<typename T>
class Node {
public:
    T data;
    std::shared_ptr<Node<T>> next;

    explicit Node(const T &value) : data(value), next(nullptr) {}
};

template<typename T>
class [[maybe_unused]] GLinkedList {
private:
    typedef std::shared_ptr<Node<T>> NodePtr;

    NodePtr _head;
    NodePtr _tail;
    int _length;

public:
    // 入队
    void append(const T &value) {
        _tail->next = std::make_shared<Node<T>>(value);
        _tail = _tail->next;
        _length++;
    }

    // 在队列中查找元素
    NodePtr find(const int &index) const {
        auto traveler = _head->next;
        int curIndex = 0;
        while (traveler && curIndex < index) {
            traveler = traveler->next;
            curIndex++;
        }
        if (curIndex == index) {
            return traveler;
        }
        return nullptr;
    }

    // 查找元素的上一个
    NodePtr findPre(const int &index) const {
        auto traveler = _head;
        int curIndex = -1;
        while (traveler && curIndex < index - 1) {
            traveler = traveler->next;
            curIndex++;
        }
        if (curIndex == index - 1) {
            return traveler;
        }
        return nullptr;
    }

    // 在指定位置插入元素
    void insert(const int &index, const T &value) {
        if (auto preNode = findPre(index)) {
            auto newNode = std::make_shared<Node<T>>(value);
            newNode->next = preNode->next;
            preNode->next = newNode;
            _length++;
        }
        throw std::out_of_range("Index out of range.");
    }

    // 删除指定位置的元素
    void remove(const int &index) {
        if (auto preNode = findPre(index)) {
            preNode->next = preNode->next->next;
            _length--;
        }
        throw std::out_of_range("Index out of range.");
    }

    // 获取指定位置的元素
    T get(const int &index) const {
        if (auto curNode = find(index)) {
            return curNode->data;
        }
        return NULL;
    }

    // 查找元素的位置
    int search(const T value) const {
        auto traveler = _head->next;
        int curIndex = 0;
        while (traveler) {
            if (traveler->data == value) {
                return curIndex;
            }
            traveler = traveler->next;
            curIndex++;
        }
        return -1;
    }

    // 清空队列
    void clear() {
        // 重开虚拟头，智能指针将自动释放原来的链表
        _head = std::make_shared<Node<T>>(0);
        _tail = _head;
        _length = 0;
    }

    // 获取队列的大小
    int length() const {
        return _length;
    }

    // 逆转队列
    void reverse() {
        if (_length <= 1) return;
        _tail = _head->next;
        NodePtr preNode = _head, curNode = preNode->next, nextNode;
        while (curNode) {
            nextNode = curNode->next;
            curNode->next = preNode;
            preNode = curNode;
            curNode = nextNode;
        }
        _head->next = preNode;
        _tail->next = nullptr;
    }

    // 遍历队列
    // 利用函数对象创造不同方法的 traverse
    template<typename Func>
    void traverse(Func func) {
        auto traveler = _head->next;
        while (traveler) {
            func(traveler);
            traveler = traveler->next;
        }
    }

    // 遍历队列并输出
    // 不传参数默认是输出元素
    void traverse() {
        std::cout << "Current LinkedList:" << std::endl;
        // 函数对象配合匿名函数
        traverse([](NodePtr node) {
            std::cout << node->data << ' ';
        });
    }

    // 队列求和 类型断言
    // 仅对 int 实现, 采用 SFINAE
    typename std::enable_if<std::is_integral<T>::value, int>::type
    sum() {
        T sum = 0;
        // lambda 表达式显示捕获, 待深入学习
        traverse([&sum](NodePtr node) {
            sum += node->data;
        });
        return sum;
    }

    GLinkedList() : _head(std::make_shared<Node<T>>(0)), _tail(_head), _length(0) {}
};
